package 剑指offer;

public class 剑指Offer51数组中的逆序对 {
    public int reversePairs(int[] nums) {

        //否则就说明至少存在两个元素，开始进行归并排序
        return mergeHelper(nums,0,nums.length-1);
    }
    private int mergeHelper(int[] arr,int l,int r){
        if(l >= r){
            return 0;
        }
        //否则存在多个元素
        //将左边的的求逆序的个数交给这个方法
        int mid = l + (r - l) / 2;
        int leftCount = mergeHelper(arr,l,mid);
        int rightCount = mergeHelper(arr,mid+1,r);

        if(arr[mid] <= arr[mid+1]){
            return leftCount + rightCount;
        }

        return leftCount + rightCount + merge(arr,l,mid,r);
    }

    private int merge(int[] arr,int l,int mid ,int r){
        int[] aux = new int[r-l+1];
        int count = 0;
        for(int i = l; i <= r;i ++){
            aux[i-l] = arr[i];
        }
        int j = mid + 1;
        int i = l;
        for(int k = l; k <= r;k++){
            if(i > mid){
                arr[k] = aux[j - l];
                j ++;
            }else if(j > r){
                arr[k] = aux[i - l];
                i++;
            }else if(aux[i-l] <= aux[j-l]){
                arr[k] = aux[i-l];
                i++;
            }else{
                count += mid-i+1;
                arr[k] = aux[j-l];
                j++;
            }
        }
        return count;
    }
}
